1. Field of the Invention
This invention relates to processing of document images, and in particular, it relates to a process for removal of horizontal, vertical, or other straight lines from the document image while preserving the continuity of character strokes that intersect such lines.
2. Description of Related Art
In digital processing of document images, i.e., digital images that represent documents, it is often desirable to remove horizontal and vertical lines within the image. Examples of such straight lines include underlines in text, and horizontal and vertical lines of tables and forms. For example, when applying OCR (optical character recognition) to a document image to extract text of the document, if is often desirable to remove underlines first because they interfere with character recognition. In another example, digital processing of images of bank checks often requires removal of various lines. The document image is typically obtained by scanning or photographing a hard copy document; line detection and removal can be performed before or after binarization which is a process that converts a gray-scale document image into a binary document image.
Various line detection and removal method have been proposed. Detecting line segments can be performed on binary images. This category of methods include run length coding, least square fitting, Hough transform, and mathematical morphology with a flat linear structuring element that is symmetric with respect to the neighborhood center. Least square fitting method can be affected significantly by noises. Run length coding is based on searching or tracing of local line-like structures as candidates of line segments. The block-adjacency graph (BAG) is a generalization of the line-adjacency graph where adjacency horizontal runs are merged. See, for example, Bin Yu and Anil K. Jain, “A Generic System for Form Dropout”, IEEE Trans. PAMI, Vol. 18, No. 11, 1996 (hereinafter “Yu et al. 1996”). However, Run length code and its extension BAG methods often do not deliver satisfactory result where the lines to be removed are in disconnected pieces. In BAG-based system, both handwriting and machine printed characters can be extracted only if the blank form document is offered to generate form-structure template. Hough transform is extremely time-consuming, since it converts every pixel in the image into Hough parameter space through expensive trigonometric computation.
Detecting line segments can also be performed on gray-level document images. Typical methods include vectorization-based tracing, mathematical morphology, and line segment detector (LSD). LSD-based method does not work well for document images because LSD is based on gradient-fitting. Complicate text field gradient map can change local line gradient distribution.
Many existing line removal methods do not preserve the complete strokes of handwriting and printed characters that intersect the lines; as a result, individual symbols sometimes become disintegrated into several broken parts, or parts of the symbols are sometimes truncated, in the binarized image after line removal. FIG. 7 illustrates some examples of underline removal using a conventional method, where the result of broken characters and truncation can be seen. Some methods attempt to re-connect broken characters after line removal. For example, Yu et al. 1996 describes an approach to line removal which includes localization of lines, separation of characters and lines, and reconstruction of broken strokes introduced during separation.
Xiangyun Ye, Mohamed Cheriet, Ching Y. Suen, and Ke Liu, “Extraction of bankcheck items by mathematical morphology,” International J. on Document Analysis and Recognition (1999) (hereinafter “Ye et al. 1999”) describes a method of extracting characters from bank check images, which uses mathematical morphology for line detection. Broken strokes after line removal are then restored using dynamic kernels. In Ye's stroke restoration method, correct local orientation around the region of line and stroke intersection is needed to find the right dynamic kernels for mending broken stroke, but local orientation is dependent on the length and width of touching line and stroke.